package leetcode

type ListNode struct {
	Val  int
	Next *ListNode
}

func merge2Lists(l1, l2 *ListNode) *ListNode {
	resHead := ListNode{0, nil}
	resTail := &resHead
	for l1 != nil && l2 != nil {
		if l1.Val > l2.Val {
			resTail.Next = l2
			l2 = l2.Next
		} else {
			resTail.Next = l1
			l1 = l1.Next
		}
		resTail = resTail.Next
	}
	if l1 != nil {
		resTail.Next = l1
	}
	if l2 != nil {
		resTail.Next = l2
	}
	return resHead.Next
}

func mergeRange(lists []*ListNode, left, right int) *ListNode {
	if left == right {
		return lists[left]
	}
	if left+1 == right {
		return merge2Lists(lists[left], lists[right])
	}
	mid := (left + right) >> 1
	leftPtr := mergeRange(lists, left, mid)
	rightPtr := mergeRange(lists, mid+1, right)
	return merge2Lists(leftPtr, rightPtr)
}

func mergeKLists(lists []*ListNode) *ListNode {
	length := len(lists)
	if length == 0 {
		return nil
	}
	return mergeRange(lists, 0, length-1)
}
